import java.lang.reflect.Array;
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
       this.val = val;
       this.left = left;
       this.right = right;
   }
}

class Solution {
    public int findLHS(int[] nums) {
        HashMap < Integer, Integer > map = new HashMap < > ();
        int res = 0;
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int key: map.keySet()) {
            if (map.containsKey(key + 1))
                res = Math.max(res, map.get(key) + map.get(key + 1));
        }
        return res;
    }






    public int findLHS1(int[] nums) {
        int sum=0;
        for(int i=0;i< nums.length;i++){
            int count=0;
            boolean bool=false;
            for(int j=0;j< nums.length;j++){
                if(nums[j]==nums[i]){
                    count++;
                }else if(nums[j]+1==nums[i]){
                    count++;
                    bool=true;
                }
            }
            if(bool){
                sum=Math.max(sum,count);
            }
        }
        return sum;
    }





    public String longestWord(String[] words) {
        String ans="";
        Set<String> wordset=new HashSet();
        for(String s:words){
            wordset.add(s);
        }
        for(String s :words){
            if(s.length()>ans.length()||s.length()==ans.length()&&s.compareTo(ans)<0){
                boolean bool=true;
                for(int i=1;i<s.length();i++){
                    if(!wordset.contains(s.substring(0,i))){
                        bool=false;
                        break;
                    }
                }
                if(bool){
                    ans=s;
                }
            }
        }
        return ans;
    }





    public double trimMean(int[] arr){
        int sum=0;
        Arrays.sort(arr);
        for(int i=arr.length/20;i<arr.length-arr.length/20;i++){
            sum+=arr[i];
        }
        double count=sum/(arr.length-arr.length*0.1);
        return count;

    }







    public int[] arrayRankTransform(int[] arr) {
        int[] ret=new int[arr.length];
        ret=arr.clone();
        Arrays.sort(ret);
        Map<Integer,Integer> map=new HashMap<>();
        int index=1;
        for(int i=0;i<ret.length;i++){
            if(i>0&&ret[i]!=ret[i-1]){
                map.put(ret[i],index);
                index++;
            }else if(i==0){
                map.put(ret[i],index);
                index++;
            }
        }
        for(int i=0;i<arr.length;i++){
            arr[i]=map.get(arr[i]);
        }
        return arr;
    }




    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> list=new ArrayList<>();
        int tmp=Integer.MAX_VALUE;
        int sum=0;
        List<Integer> ret=new ArrayList<>();
        for(int i=0;i<arr.length;i++){
            if(i+1<arr.length){
                sum=tmp;
                if(Math.min(tmp,arr[i+1]-arr[i])==arr[i+1]-arr[i]){
                    tmp=arr[i+1]-arr[i];
                    if(sum!=tmp){
                        list.clear();
                    }
                    ret.add(arr[i]);
                    ret.add(arr[i+1]);
                    list.add(new ArrayList<>(ret));
                    ret.clear();
                }else{
                    continue;
                }
            }
        }
        return list;
    }






    public int[] kWeakestRows(int[][] mat, int k) {
        int[] arr=new int[mat.length];
        int[] list=new int[k];
        for(int i=0;i<mat.length;i++){
            arr[i]=count(mat[i])*100+i;
        }
        Arrays.sort(arr);
        for(int i=0;i<k;i++){
            list[i]=arr[i]%100;
        }
        return list;
    }
    public int count(int[] arr){
        int sum=0;
        for(int n :arr){
            if(n==0){
                break;
            }
            sum+=n;
        }
        return sum;
    }






    public boolean checkIfExist(int[] arr) {
        int len=arr.length;
        int[] ret=new int[len];
        for(int i=0;i<len;i++){
            ret[i]=arr[i]*2;
        }
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(arr[i]==ret[j]&&i!=j){
                    return true;
                }
            }
        }
        return false;
    }





    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums);
        List<Integer> list=new ArrayList<>();
        int count=0;
        for(int n :nums){
            count+=n;
        }
        int sum=0;
        for(int i=nums.length-1;i>=0;i--){
            sum+=nums[i];
            list.add(nums[i]);
            if(sum>count-sum){
                break;
            }
        }
        return list;
    }







    public int[] findErrorNums(int[] nums) {
        int[] arr=new int[2];
        Arrays.sort(nums);
        int prev=0;
        int len=nums.length;
        for(int i=0;i<len;i++){
            int cur=nums[i];
            if(prev==cur ){
                arr[0]=prev;
            }else if(cur-prev>1){
                arr[1]=prev+1;
            }
            prev=cur;
        }
        if(nums[len-1]!=len){
            arr[1]=len;
        }
        return arr;
    }






    public double average(int[] salary) {
        Arrays.sort(salary);
        double count=0.0;
        for(int i=1;i<salary.length-1;i++){
            count+=salary[i];
        }
        return (count/(salary.length-2));
    }




    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        int sum=sum=arr[1]-arr[0];;
        for(int i=1;i<arr.length-1;i++){
            if(arr[i+1]-arr[i]!=sum){
                return false;
            }
        }
        return true;
    }



    public int specialArray(int[] nums) {
        int max=0;
        for(int n :nums){
            if(n>max){
                max=n;
            }
        }
        int[] arr=new int[max+1];
        for(int n : nums){
            arr[n]++;
        }
        int sum=0;
        for(int i=max;i>=0;i--){
            sum+=arr[i];
            if(sum==i){
                return i;
            }
        }
        return -1;
    }
}
public class prog {



    public static void shellSort(int[] arr,int gap){//哈希排序
        for(int i=gap;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(arr[j]>tmp){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }




    public static void selectSort(int[] arr){//选择排序
        for(int i=0;i<arr.length-1;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    int tmp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=tmp;
                }
            }
        }
    }




    public static void siftDown(int[] arr,int root,int len){//堆排序
        int left=root;
        int right=root*2+1;
        while(right<len){
            if(right+1<len&&arr[right]<arr[right+1]){
                right++;
            }
            if(arr[right]>arr[left]){
                int tmp=arr[right];
                arr[right]=arr[left];
                arr[left]=tmp;
                left=right;
                right=2*left+1;
            }else{
                break;
            }
        }
    }
    public static void createHeap(int[] arr){//堆排序
        for(int i=(arr.length-1-1)/2;i>=0;i--){
            siftDown(arr,i,arr.length);
        }
    }
    public static void heapSort(int[] arr){//堆排序
        createHeap(arr);
        int end=arr.length-1;
        while(end>0){
            int tmp=arr[0];
            arr[0]=arr[end];
            arr[end]=tmp;
            siftDown(arr,0,end);
            end--;
        }
    }



    public static void bubbleSort(int[] arr){//冒泡排序
        for(int i=0;i<arr.length-1;i++){
            boolean bool=true;
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=tmp;
                    bool=false;
                }
            }
            if(bool){
                break;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
        bubbleSort(arr);
//        heapSort(arr);
//        selectSort(arr);
        System.out.println(Arrays.toString(arr));
//        int gap=arr.length;
//        while(gap>1){
//            gap=gap/3+1;
//            shellSort(arr,gap);
//        }
//        System.out.println(Arrays.toString(arr));
    }
}
